package com.algorithm.code.array;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Objects;

/**
 * @program: study
 * @className: GenericArray
 * @description: 动态扩容数组
 * 1. 支持查查删改
 * 2. 支持动态扩容
 * 3. 不支持null值
 * @author: kukuxiahuni
 * @create: 2020-01-13 15:10
 * @version: v1.0
 **/
public class GenericArray<T> {

    /**
     * 默认大小16
     */
    private final static int CAPACITY = 16;
    private final Object[] DEFAULT_EMPTY_ARRAY = {};
    /**
     * 数组大小
     */
    private T[] data;
    /**
     * 数值数量
     */
    private int size;


    /**
     * 功能描述: TODO
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 3:17 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 3:17 下午
     **/
    public GenericArray(Class<T> clazz, int capacity) {
        this.size = 0;
        this.data = (T[]) Array.newInstance(clazz, capacity);
    }

    /**
     * 功能描述: TODO
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 3:30 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 3:30 下午
     **/
    public GenericArray(Class<T> tClass) {
        this(tClass, CAPACITY);
    }

    public static void main(String[] args) {

        GenericArray<String> stringArray = new GenericArray<>(String.class);

        for (int i = 0; i < 40; ++i) {
            stringArray.add("faf");
        }
        stringArray.add(4, "fafaf");

        int count = 0;
        for (String s : stringArray.toArray()) {
            System.out.println(s);
            ++count;
        }

        System.out.println(count);

        ArrayList<String> arrayList = new ArrayList<>();
        for (int i = 0; i < 40; ++i) {
            arrayList.add("faf");
        }
        arrayList.add(4, "fafafaR");
        System.out.println(arrayList.size());

    }

    /**
     * 功能描述: TODO
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 3:51 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 3:51 下午
     **/
    public int getCapacity() {
        return this.data.length;
    }

    /**
     * 功能描述: 获取数组元素数量
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 3:52 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 3:52 下午
     **/
    public int count() {
        return this.size;
    }

    /**
     * 功能描述: 判断当前数组是否为空
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 3:52 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 3:52 下午
     **/
    public boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 功能描述: TODO
     *
     * @return oldValue: 返回该位置上的原有值
     * @param:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 3:53 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 3:53 下午
     **/
    public T set(int index, T value) {
        this.checkIndex(index);
        T oldValue = this.data[index];
        this.data[index] = value;
        return oldValue;
    }

    /**
     * 功能描述: 根据指定的索引查询相关的值，没有的话返回空
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 3:31 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 3:31 下午
     **/
    public T get(int index) {
        this.checkIndex(index);
        return this.data[index];
    }

    /**
     * 功能描述: 查看数组是否包含元素value
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 3:59 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 3:59 下午
     **/
    public boolean contains(T value) {
        if (Objects.isNull(value)) {
            return false;
        }
        for (T t : this.data) {

            if (value.equals(t)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 功能描述: 获取指定元素的下标，未获取则返回-1
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 4:03 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 4:03 下午
     **/
    public int find(T value) {

        if (Objects.isNull(value)) {
            return -1;
        }

        for (int i = 0; i < this.size; ++i) {
            if (data[i].equals(value)) {
                return i;
            }
        }

        return -1;
    }

    /**
     * 功能描述: 将数组元素缩容至size的大小，以减小空间占用
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 4:21 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 4:21 下午
     **/
    public void trimToSize() {
        /**
         * 如果当前数组的size小于capacity值，则进行数组缩容
         */
        if (this.size < this.data.length) {
            this.data = this.isEmpty() ? (T[]) DEFAULT_EMPTY_ARRAY : Arrays.copyOf(this.data, this.size);
        }
    }

    /**
     * 功能描述: 在指定位置添加数据
     * 1. 如果超出最大容量，则扩容
     * 2. 数据size + 1
     * add 方法会有bug: 如果在已经有值的位置进行add，会覆盖原有的值，并++size。
     * add方法不应该在[0,size-1]范围内进行add
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 4:06 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 4:06 下午
     **/
    public void add(int index, T value) {
        checkIndexForAdd(index);
        if (index == data.length) {
            this.resize(2 * data.length);
        }

        this.data[index] = value;
        ++size;
    }

    /**
     * 功能描述: TODO
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 5:21 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 5:21 下午
     **/
    public void addFirst(T value) {
        this.add(0, value);
    }

    /**
     * 功能描述: TODO
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 5:21 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 5:21 下午
     **/
    public void addLast(T value) {
        this.add(size, value);
    }


    /**
     * 功能描述: 插入元素
     * 默认向数组的最后一个位置插入
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 3:35 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 3:35 下午
     **/
    public void add(T value) {
        if (Objects.isNull(value)) {
            return;
        }

        this.addLast(value);
    }

    /**
     * 功能描述: 移除指定位置元素
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 5:23 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 5:23 下午
     **/
    public T remove(int index) {

        checkIndex(index);

        T oldValue = data[index];

        //删除元素需要移动位置
        for (int i = index + 1; i < size; ++i) {
            this.data[i - 1] = this.data[i];
        }

        --size;
        //将size位置元素置为空, GC回收该位置的数据
        data[size] = null;

        return oldValue;
    }

    /**
     * 功能描述: TODO
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 5:33 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 5:33 下午
     **/
    public T removeFirst() {
        return this.remove(0);
    }

    /**
     * 功能描述: 移除最后一个
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 5:33 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 5:33 下午
     **/
    public T removeLast() {
        return this.remove(size - 1);
    }

    /**
     * 功能描述: 移除指定元素
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 5:34 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 5:34 下午
     **/
    public void removeElement(T value) {

        if (Objects.isNull(value)) {
            return;
        }

        int index = this.find(value);
        if (index != -1) {
            this.remove(index);
        }
    }

    /**
     * 功能描述: TODO
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 5:42 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 5:42 下午
     **/
    public T[] toArray() {
        return Arrays.copyOf(this.data, size);
    }


    /**
     * 功能描述: 检查索引是否越界(超过size大小，或小于0)
     * set是在 [0, size]之间操作
     *
     * @param index:数组索引
     * @throws ArrayIndexOutOfBoundsException: 数组越界异常
     * @适用范围： 近限于set场景
     * @auther: kukuxiahuni
     * @date: 2020/1/13 3:56 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 3:56 下午
     **/
    private final void checkIndex(int index) {
        if (index >= this.size || index < 0) {
            throw new ArrayIndexOutOfBoundsException("索引越界");
        }
    }

    /**
     * 功能描述: 添加元素时，校验索引是否越界
     *
     * @param index: 这个保证了数组添加元素时，不会中间出现空的格子
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 4:10 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 4:10 下午
     **/
    private final void checkIndexForAdd(int index) {

        if (index > this.size || index < 0) {
            throw new ArrayIndexOutOfBoundsException("索引越界");
        }
    }

    /**
     * 功能描述: 扩容
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/13 5:17 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/13 5:17 下午
     **/
    private void resize(int capacity) {
        this.data = Arrays.copyOf(this.data, capacity);
    }


}
